/**
 * https://leetcode-cn.com/problems/coin-change/
 * 零钱兑换
 * @param coins 
 * @param amount 
 */
const coinChange = (coins: number[], amount: number) => {
    if (coins.length === 0) return -1;
    if (amount === 0) return 0
    // [1, 2, 5] 11
    // dp[11] = dp[11 - 5] + 1 
    // dp[11] = dp[11 - 2] + 1
    // dp[11] = dp[11 - 1] + 1
    // dp[11] = min{dp[11 - 5], dp[11 - 2], dp[11 - 1]} + 1

    // dp[i] 凑够i元所需要的最小硬币数量
    // 状态转移方程: dp[i] = min {dp[i - c[k]]} + 1， k表示coins的每一项
    const dp: number[] = new Array(amount + 1).fill(-1)
    dp[0] = 0;
    // [0, -1, -1, ..., -1]
    for (let i = 1; i <= amount; i++) {
        // min表示的是交换coins所有值完之后的最小值
        let min = Number.MAX_SAFE_INTEGER;
        for (const v of coins) {
            // 当前的钱不能兑换
            if (i < v) continue;

            // i - v 表示的值交换完后剩余的钱 

            // dp[i - v] < 0 表示的是amount为i元时没有硬币凑出该值
            // dp[i - v] >= min 表示的是如果使用该该币后仍然大于等于最小值，说明可以不用改币值
            if (dp[i - v] < 0 || dp[i - v] >= min) continue

            // 更新min的值
            min = dp[i - v] + 1;
            // 或者 min = Math.min(dp[i - v] + 1, min)
        }
        // [0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
        // 如果当前的钱能够交换, 就赋值给dp[i]
        if (min !== Number.MAX_SAFE_INTEGER) {
            dp[i] = min;
        }
    }

    return dp[amount]
}




const coinChange2 = (coins: number[], amount: number): number => {
    // 边界判断
    if (coins.length === 0) return -1
    if (amount === 0) return 0

    // 创建dp, dp[i] 表示凑够i元的最小硬币数量
    // 状态转移方程: dp[i] = min{dp[i - k] + 1, dp[i]}
    const dp: number[] = new Array(amount + 1).fill(amount + 1);
    // [1, 2, 5] 11
    dp[0] = 0
    for (let i = 1; i <= amount; i++) {
        for (const v of coins) {
            if (i >= v) {
                // 当值前能够兑换
                dp[i] = Math.min(dp[i], dp[i - v] + 1)
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount]
};



